/*
 * BinaryHeap.cpp
 *
 *  Created on: 28/05/2011
 *      Author: frandres
 */

#include "BinaryHeap.h"

BinaryHeap::BinaryHeap()
{
	elements = new std::vector<FifteenPuzzleNodeA *>();
}

bool BinaryHeap::empty()
{
	return elements->empty();
}

int BinaryHeap::size(){
	return elements->size();
}

unsigned int  BinaryHeap::getFatherIndex(int i)
{
	return (i-1)/2;
}

unsigned int  BinaryHeap::getChildIndex(int i, int j)
{
	return (2*i)+j;
}

BinaryHeap::~BinaryHeap()
{/*
	vector <FifteenPuzzleNodeA *>:: iterator eraser = elements->begin();
	for(; eraser != elements->end(); eraser++)
	{

		delete (*eraser);
		//
	}*/
	delete (elements);
}

void BinaryHeap::insertElement(FifteenPuzzleNodeA * newElement)
{
	if (newElement->getHeapIndex() != UINT_MAX){
		cout<< "Warning. Intentando insertar algo que ya está en la lista\n";
		return;
	}

	elements->push_back(newElement);
	newElement->setHeapIndex(elements->size()-1);
	if (elements->size()-1>0){
		upHeap(newElement,elements->size()-1);
	}
}

void BinaryHeap::upHeap(FifteenPuzzleNodeA * node,int position)
{

	if (node->getG() <= elements->at(getFatherIndex(position))->getG())
	{
		return;
	}

	// Swapear con el padre.
	swap(position,getFatherIndex(position));

	if (getFatherIndex(position)>0)
	{
		upHeap(node,getFatherIndex(position));
	}
}
void BinaryHeap::swap(unsigned int pos1, unsigned int pos2)
{

	elements->at(pos1)->setHeapIndex(pos2);
	elements->at(pos2)->setHeapIndex(pos1);

	FifteenPuzzleNodeA * temp = elements->at(pos1);
	elements->at(pos1) = elements->at(pos2);
	elements->at(pos2) = temp;

}

void BinaryHeap::removeElement(unsigned int position)
{
	if (position == UINT_MAX){
		cout<< "Warning. Intentando borrar algo que no está en la lista\n";
		return;
	}

	if (elements->size()==0){
		cout<< "Warning. Intentando borrar en una lista vacia";
		return;
	}
	swap (position,elements->size()-1);
	elements->at(elements->size()-1)->setHeapIndex(UINT_MAX);

	elements->pop_back();
	downHeap(position);
}

void BinaryHeap::downHeap(unsigned int position)
{

	if (getChildIndex(position,1)<elements->size() && elements->at(position)->getG() < elements->at(getChildIndex(position,1))->getG()){
		swap(position,getChildIndex(position,1));
		downHeap (getChildIndex(position,1));
	}

	if (getChildIndex(position,2)<elements->size() && elements->at(position)->getG() < elements->at(getChildIndex(position,2))->getG()){
			swap(position,getChildIndex(position,2));
			downHeap (getChildIndex(position,2));
	}
}

FifteenPuzzleNodeA *  BinaryHeap::pullMax()
{
	FifteenPuzzleNodeA * max =elements->at(0);
	removeElement(0);
	return max;
}
